Modern electronic computing systems, such as microprocessor systems, typically include processors configured to perform various computing tasks. Computer processors often include a registry file that includes a plurality of registers and holds the data employed in the various computing tasks. The processor moves data into and out of the registers in accordance with instructions that are based on high-level language instructions provided by a user or programmer.
Some computer systems employ a vector to track whether registers in the registry file are available to receive data. That is, the vector indicates whether a particular register is already in use, whether locked or holding data. In some computer systems, the vector comprises a plurality of ordered bits, wherein each bit is set to zero if the associated register is unavailable or set to one if the associated register is available to receive data. In other systems, each register includes a “free” bit indicating whether the register is available to receive data. In such systems, there are various methods to construct a vector from the “free” bits, as one skilled in the art will understand.
In earlier systems, registry files were relatively small, and operated in an environment where, on average, at most only one instruction issued each clock cycle. Generally, the trend in industry today is to provide processors with larger and larger registry files, in order to support more complex instructions and register renaming conventions. As registry files increase in size, the amount of time needed to find a free registry, and the number of entries required per cycle for register renames, increases as well. This increase is particularly noticeable when two empty registers need to be found. In this case, searching for empty registers one at one time is both inefficient and time consuming.
In order to decrease the amount of time needed to find an empty registry entry, that is, an empty register, programmers have sought to develop a suitable algorithm that will search for two empty registers at one time. One method commonly used divides a large registry file into two smaller blocks. This method searches each block simultaneously for one empty register each. Upon finding a free entry in one or both of the smaller blocks, this method constructs a one-hot vector to show the position of the free entry and raises a signal, “found one.”
But this method suffers from a significant disadvantage. Specifically, a problem occurs with this method when empty registers exist only in one of the two blocks, such as, for example, when one of the two blocks experiences high demand that results in no free entries in that block. In this case, the algorithm reports only one empty register location, even though more than one register may be available in the block.
To overcome this disadvantage, a somewhat improved, “intuitive” method searches a single block for two empty registers. In particular, the intuitive method attempts to identify two free entries in a single block, thereby increasing the yield of free entries. The intuitive approach attempts to spend the same amount of time searching for two free entries in a single block that would be spent using the earlier methods for searching for a single free entry in two blocks.
Referring now to FIG. 1, which depicts a block diagram illustrating a prior art computer system, a computer system 100 includes a registry file 102. Registry file 102 is an otherwise conventional registry file, also sometimes known as a “register file,” and includes a plurality of entries 104, each coupled to an associated “free” bit 106. Generally, each free bit 106 is configured in one of two states that indicate whether the associated entry 104 is empty or otherwise available to receive data. A plurality of signal lines 108 taps each of the plurality of free bits 106, coupling together to form a bus 110. As illustrated, bus 110 is n-bits wide, where n indicates the number of registry entries 104 in registry file 102.
Computer system 100 includes “One's Hot” vector (OHV) module 120. Generally, OHV module 120 couples to bus 110 and receives the plurality of signals representing the state of the free bits 106. In one embodiment, OHV module 120 traverses the plurality of signals represented by bus 110, and generates one or more vectors, each representing the state of the free bits 106 in a manner that indicates whether each entry 104 is empty or otherwise available to receive data.
One skilled in the art will understand that OHV module 120 can generate an OHV in a variety of matters, including, in one embodiment, a transformation of bus 110 into a conventional ones-hot vector. In the illustrated embodiment, OHV module 120 generates two OHVs, OHV 122 and OHV 124. OHV 122 and OHV 124 are otherwise conventional ones-hot vectors, and are n-bits wide, where n indicates the number of registry entries 104 in registry file 102.
While OHV module 120 generates OHVs that indicate which, if any, of the registry entries 104 are available to receive data, most typical computer systems 100 also require some general indication of whether there are any available entries at all. Typically, this indication is in the form of a signal, sometimes called “found one,” which indicates that there is at least one free entry in registry file 102. Typical computer systems 100 use this “found one” signal for control logic.
In the illustrated embodiment, computer system 100 includes an OR tree 130 to generate a “found one” signal. Generally, OR tree 130 is a collection of otherwise conventional logic OR gates, arranged in a tree configuration. OR tree 130 couples to bus 110, and generates a “found one” signal 132 based on the states of the signals comprising bus 110. In one embodiment, “found one” signal 132 is a single bit indicating whether any of the free bits 106 are set, that is, whether there is at least one entry 104 available to receive data. One skilled in the art will understand that OR tree 130 can also generate the “found one” signal in a variety of ways in addition to or instead of by means of a collection of OR gates arranged in a tree configuration. As such, OR tree 130 generally represents these alternate means.
Additionally, some computer systems 100 require OR tree 130 to generate a “found one” signal 132 for each OHV generated by OHV module 120. For simplicity, the illustrated embodiment omits additional “found one” signals. In some embodiments, OHV module 120 comprises a separate OR tree 130 to generate a separate “found one” signal for each OHV.
One skilled in the art will understand that some computer systems 100 require an additional “found two” signal, indicating whether there are at least two entries 104 that are available to receive data. The “intuitive method” described above operates to generate a “found two” signal from OHV 122, OHV 124, and “found one” signal 132. Specifically, computer system 100 includes an exclusive OR (XOR) gate 140 coupled to OHV module 120.
Generally, XOR gate 140 is an otherwise conventional XOR gate, configured to perform a bitwise XOR function using OHV 122 and OHV 124 as inputs. XOR gate produces an n-bit wide XOR output 142. An inverter (NOT) gate 144 couples to XOR gate 140. NOT gate 144 is an otherwise conventional NOT gate or inverter, and generates an NOT output that is the logical inverse of the XOR output 142. Thus, NOT gate 144 indicates whether there are either zero or at least two free entries indicated by OHV 122 and OHV 124.
To resolve whether the NOT output indicates zero or at least two free entries, computer system 100 includes logic AND gate 146. AND gate 146 is an otherwise conventional AND gate and couples to NOT gate 144 and OR tree 130. AND gate 146 performs a logic AND function using the NOT output and “found one” signal 132 as inputs. As such, AND gate 146 generates a “found two” signal 150 that is raised when the NOT output indicates that there are either zero or two (or more) available entries, and the “found one” signal 132 indicates that there is at least one available entry in registry file 102.
More specifically, as one skilled in the art will understand, AND gate 146 will only produce a one if both of its inputs are ones. Therefore, if both of the “found one” signals are zeros, the output of the AND gate will be a zero, and the control logic will know that no empty registers have been found. If the output is a one, the control logic will know that two empty registers have been found. Subsequently, the control logic of computer system 100 (not shown) can combine the two one-hot vectors, for example, through using an OR gate (not shown).
However, this intuitive method suffers from the disadvantage of being very slow because it causes at least two delays. First, generating “found two” signal 150 using NOT gate 144 and AND gate 146 creates one delay. Second, combining the one-hot vectors OHV 122 and OHV 124 creates another delay. Furthermore, in typical systems, the entire process, generating signal 150 and combining OHV 122 and OHV 124, must be completed in one clock cycle.
But because creating the one-hot vectors takes most of one clock cycle, these additional delays may prevent the process from being competed in time. Generally, typical systems can generate “found two” signal 150 on the order of log2 n, where n indicates the number of entries 104 in registry file 102. One skilled in the art will understand that as n increases, the time required to generate the necessary “found two” signal may exceed the time allowed, thereby limiting the size of the registry file, or causing clock cycle time increases that may cause serious disruption to other system components or design problems.
Therefore, there is a need for a system and/or method for identifying free registry file entries, and for vector analysis, that addresses at least some of the problems and disadvantages associated with conventional systems and methods.